package william.array;

import java.util.Arrays;
import java.util.Comparator;
import java.util.LinkedList;

/**
 * @author ZhangShenao
 * @date 2024/4/10
 * @description <a href="https://leetcode.cn/problems/merge-intervals/description/?envType=study-plan-v2&envId=top-100-liked">...</a>
 */
public class Leetcode56_合并区间 {
    /**
     * 借助排序实现
     * 1. 将区间数组按照左端点升序的顺序排序
     * 2. 维护merged数组,保存合并后的区间
     * 3. 遍历intervals区间数组:
     * - 如果当前区间是第一个区间,则放入merged数组
     * - 如果当前区间的左端点大于merged数组中最后一个区间的右端点,则无需合并,直接将当前区间放入merged数组
     * - 如果当前区间的左端点小于等于merged数组中最后一个区间的右端点,则需要合并,取出merged数组中最后一个区间,将其右端点更新为原值和当前区间值的最大值
     * <p>
     * 时间复杂度O(N*logN) 排序O(N*logN)+遍历数组O(N)
     * 空间复杂度O(N) 额外申请了一个merged数组,长度为N
     */
    public int[][] merge(int[][] intervals) {
        //边界条件校验
        if (intervals == null || intervals.length < 1) {
            return new int[0][0];
        }

        //将区间数组按照左端点升序的顺序排序
        Arrays.sort(intervals, Comparator.comparingInt(i -> i[0]));

        //维护merged数组,保存合并后的区间
        LinkedList<int[]> merged = new LinkedList<>();

        //遍历区间数组
        for (int[] interval : intervals) {
            if (merged.isEmpty()) { //第一个区间,直接放入merged数组
                merged.addLast(interval);
                continue;
            }

            //取出merged数组中的最后一个区间
            int[] last = merged.getLast();

            if (interval[0] > last[1]) { //当前区间的左端点大于最后一个区间的右端点,则无重合,无需合并,直接将当前区间放入merged数组
                merged.addLast(interval);
                continue;
            }

            //合并区间,将最后一个区间的右端点,更新为原始值和当前区间右端点的最大值
            last[1] = Math.max(last[1], interval[1]);
        }

        //返回结果
        return merged.toArray(new int[merged.size()][]);
    }
}
